/*
2.给你单链表的头节点 head，请你反转链表，并返回反转后的链表
    [
        11 -> 22 -> 33 -> 44
        44 -> 33 -> 22 -> 11
    ]
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* 定义一个链表结点结构体 */
typedef struct LinkNode
{
    int data;
    struct LinkNode * next;
}LinkNode;

/* 创建链表 */
static LinkNode * createList(int *array, int size)
{
    /* 定义链表头尾指针 */
    LinkNode * head = NULL;
    LinkNode * tail = NULL;
    for (int idx = 0; idx < size; idx++)
    {
        /* 为新节点分配内存 */
        LinkNode * newNode = (LinkNode *)malloc(sizeof(LinkNode) * 1);
        if (newNode == NULL)
        {
            perror("mallco error");
            return NULL;
        }
        /* 清除脏数据 */
        memset(newNode, 0, sizeof(LinkNode) * 1);

        newNode->data = array[idx];//赋值
        newNode->next = NULL;//初始化

        if (head == NULL)
        {
            /* 链表为空，则新节点就是头节点 */
            head = newNode;
        }
        else 
        {
            tail->next = newNode;
        }
        tail = newNode;
    }
    /* 返回链表的头结点 */
    return head;
}

/* 打印链表 */ 
void printList(LinkNode *head) 
{  
    while (head != NULL) 
    {  
        printf("%d ", head->data);  
        head = head->next;  
    }  
    printf("\n");  
}  
  
/* 释放链表内存 */
int freeList(LinkNode *head) 
{
    /* 从头结点开始遍历 */  
    LinkNode *current = head;  
    while (current != NULL) 
    {  
        LinkNode *next = current->next;  
        free(current);  
        current = next;  
    }
    return 0;
}  
/* 反转链表函数 */   
LinkNode * reverseList(LinkNode* head) 
{  
    LinkNode *prev = NULL;  
    LinkNode *current = head;  
    LinkNode *next_temp = NULL;  
  
    while (current != NULL) 
    {  
        /* 保存当前节点的下一个节点 */   
        next_temp = current->next;  
        /* 修改当前节点的next指针指向前一个节点 */   
        current->next = prev;  
        /* 移动指针到下一个节点 */   
        prev = current;  
        current = next_temp;  
    }  
    /* 返回新的头节点 */   
    return prev;  
}  

int main()
{
    int array[] = {1, 2, 3, 4, 5};  
    int size = sizeof(array) / sizeof(array[0]);  
  
    /* 创建链表 */   
    LinkNode *head = createList(array, size);  
      
    /* 打印原始链表 */   
    printf("Original List: ");  
    printList(head);  
  
    /* 反转链表 */   
    LinkNode *reversed_head = reverseList(head);  
  
    /* 打印反转后的链表 */   
    printf("Reversed List: ");  
    printList(reversed_head);  
  
    /* 释放链表内存 */   
    freeList(reversed_head);  
  
    return 0; 

}